Матч 19, Распродажа (SalePitch)

Недавно Ваш босс решил продавать товар в формате “BUY X GET Y FREE”, где X и Y – целые числа. Например, если Вы хотите получить за товар $4.00, который реально продается за $6.00, то можно написать: “BUY 2 GET 1 FREE”.

Строка regular содержит реальную продажную цену товара, а sale – желаемую цену. Вернуть строку в формате “BUY X GET Y FREE”, где X и Y – положительные целые числа без ведущих нулей. Значения X и Y должны быть наименьшими возможными. Например, вместо "BUY 4 GET 2 FREE" следует писать "BUY 2 GET 1 FREE".

Класс: SalePitch

Метод: string buyXGetY(string regular, string sale)

Ограничения: regular и sale имеют формат “$X.ZY”, где 0 £ X £ 1000, 0 £ Y, Z £ 9, sale £ regular, ни одна из строк не содержит “0.00”.

Вход. Две строки: реальная продажная цена товара regular и желаемая цена sale.

Выход. Строка в формате “BUY X GET Y FREE”.

Пример входа

regular	sale
"$6.00"	"$4.00"
"$100.00"	"$0.50"
"$12.34"	"$8.64"

Пример выхода

"BUY 2 GET 1 FREE"

"BUY 1 GET 199 FREE"

"BUY 432 GET 185 FREE"

РЕШЕНИЕ

наибольший общий делитель

Из условия задачи следует равенство: sale * (X + Y) = regular * X. Откуда sale * Y = (regular – sale) * X. Занесем в переменные reg и sal соответственно реальную и желаемую цену товара в центах. Положим reg = reg – sal. Остается найти наименьшие X и Y, для которых

sal * Y = reg * X

Очевидно, что пара (X, Y) = (sal, reg) является решением. Остается разделить эти значения на их наибольший общий делитель.

ПРОГРАММА

#include <cstdio>

#include <string>

using namespace std;

int gcd(int a, int b)

{

return (!b) ? a : gcd(b,a % b);

}

class SalePitch

{

public:

string buyXGetY(string regular, string sale)

{

char res[50];

double r, s;

int reg, sal, d;

sscanf(regular.c_str(),"$%lf",&r); reg = (int)((r + 0.001) * 100);

sscanf(sale.c_str(),"$%lf",&s); sal = (int)((s + 0.001) * 100);

reg = reg - sal;

d = gcd(reg,sal); reg /= d; sal /= d;

sprintf(res,"BUY %d GET %d FREE",sal,reg);

return (string)res;

}

};